
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1658. -- [Usaco2006 Mar]Water Slides -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1658: [Usaco2006 Mar]Water Slides</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>52&nbsp;&nbsp;<span class=green>Solved: </span>27<br>[<a href='submitpage.php?id=1658'>Submit</a>][<a href='problemstatus.php?id=1658'>Status</a>][<a href='bbs.php?id=1658'>Discuss</a>]</center><h2>Description</h2><div class=content>It's a hot summer day, and Farmer John is letting Betsy go to the
water park where she intends to ride every single slide. The water
park has N (1 <= N <= 10,000) platforms (numbered 1..N) from which
to enter the M (1 <= M <= 10,000) water slides. Each water slide
starts at the top of some platform and ends at the bottom of some
platform (possibly the same one). Some platforms might have more
than one slide; some might not have any.

The park is very thin, so the platforms lie along a straight line,
each platform at a position Xi (0 <= Xi <= 100,000) meters from one
end of the park. One walks from one platform to the next via a
sidewalk parallel to the line of platforms.

给出一个弱连通图.添边使其成为欧拉图,使得新边的总权值最小.新边i->j的边权定义为|X[i]-X[j]|.


The platforms of the water park are weakly connected; that is, the
park cannot be divided into two sets of platforms with no slides
running between the two sets. Both the entrance and exit to the
park are at platform 1, so Betsy will start and end there.

In order to spend more time on the slides, Betsy wants to walk as
little as possible. Find the minimum distance Betsy must travel
along the ground in order to try every slide in the park exactly
once without repeating.

</div><h2>Input</h2><div class=content>* Line 1: Two integers, N and M.

* Lines 2..N+1: Line i+1 contains one integer, Xi, the position of
        platform i.

* Lines N+2..M+N+1: Line i+N+1 contains two integers, Si and Di,
        respectively the start and end platforms of a slide.

</div><h2>Output</h2><div class=content>
* Line 1: One integer, the minimum number of meters Betsy must walk.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 7<br />
5<br />
3<br />
1<br />
7<br />
10<br />
1 2<br />
1 2<br />
2 3<br />
3 1<br />
4 5<br />
1 5<br />
4 1<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>8<br />
<br />
OUTPUT DETAILS:<br />
<br />
Betsy slides from 1 -> 2 -> 3 -> 1 -> 2, then walks a distance 2<br />
back to platform 1. She can then slide to 5, walk to 4, slide to<br />
5, walk back to 4 and slide to 1 for a total distance of 8.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1658'>Submit</a>][<a href='problemstatus.php?id=1658'>Status</a>][<a href='bbs.php?id=1658'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
